package com.company.Sort;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}23:48
 */
public class MergetSort {

    public static void main(String[] args) {
        int arr[] = {8,7,6,5,4,3,2,1};
        int temp[] = new int[arr.length];
        mergeSort(arr,0,arr.length - 1,temp);

        System.out.println(Arrays.toString(arr));
    }

    //分+合
    public static void mergeSort(int[] arr, int left, int right,int[] temp){
        if (left < right){
            int mid = (left + right) / 2;
            mergeSort(arr,left,mid,temp);//左边分
//            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);//右边分    太妙了
            //到合并时
            merge(arr,left,mid,right,temp);
        }
    }

    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;

        while (i <= mid && j <= right){
            //左边小于右边就将左边写入到数组里面
            if (arr[i] <= arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        while (i <= mid){//左边的有序序列还有剩余的元素,就全部填充到临时数组里面
            temp[t++] = arr[i++];
        }

        // 右边的序列还有剩余的元素
        while (j <= right){
            temp[t++] = arr[j++];
        }


        //将temp数组的元素拷贝到arr
        //注意：并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right){
            arr[tempLeft++] = temp[t++];
        }
    }
}
